/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
// 向右查找 直到能覆盖t，然后左指针向右收缩，找到最小值
var minWindow = function(s, t) {
  const m1 = {}
  const m2 = {}
  for(let i = 0; i < t.length; i++) {
    if(m1[t[i]]) {
      m1[t[i]]++
    } else {
      m1[t[i]] = 1
    }
  }
  let ans = s.length + 1;
  let ansStr = ""
  let left = 0
  let ansLeft = 0
  for(let i = 0; i < s.length; i++) {
    if(m2[s[i]]) m2[s[i]]++
    else m2[s[i]] = 1
    while(check(m1, m2)) {
      if(i - left + 1 < ans) {
        ans = i - left + 1
        ansLeft = left
      }
      m2[s[left]]--
      left++
      if(left > i) break
    }
  }
  return s.substring(ansLeft, ansLeft + ans + 1)
};
function check(m1, m2) {
  for(k in m1) {
    if(!m2[k] || m1[k] > m2[k]) return false
  }
  return true
}
// 第一个方法中的check花费的时间太多
var minWindow = function(s, t) {
  const m1 = {}
  let missingType = 0 // 当前字符缺失种类数
  for(let i = 0; i < t.length; i++) {
    if(m1[t[i]]) {
      m1[t[i]]++
    } else {
      missingType++ // 要找齐的种类数
      m1[t[i]] = 1
    }
  }
  let left = 0
  let ans = s.length + 1
  let start = 0
  for(let i = 0; i < s.length; i++) {
    let c = s[i]
    if(m1[c] !== undefined) m1[c]-- // 缺失个数减一
    if(m1[c] == 0) missingType-- // 缺失种类减少一个
    while(missingType == 0) {
      if(i - left + 1 < ans) {
        start = left
        ans = i - left + 1
      }
      let char = s[left]
      if(m1[char] !== undefined) m1[char]++ // 缺失个数加1
      if(m1[char] > 0) missingType++ // 种类加1
      left++
    }
  }
  if(ans == s.length + 1) return ""
  return s.substring(start, ans + start)
};